校内模拟赛提前一个小时交代码并AK祭

没事干就直接写 T4 题解吧

写得太烂了

为什么别人写的都是

则方程有解当且仅当 。

只有我的这么奇怪

前置：

表示按位或 ， 表示按位与

题意很简单

设 ，给出 ，问是否有合法的非负整数解 。

首先我们要知道

不太严谨的证明：

（以下的“每一位”指的是二进制位）

我们知道 二进制数的每一位非 0 即 1 。

对于两个二进制数的每一位而言

按位或操作：这两个数中这一位有一个或两个为 1 ，这一位就为 1 。

按位与操作：这两个数中这一位有两个为 1 ，这一位就为 1 。

普通加法操作：这两个数中这一位有一个为 1 ，这一位就为 1 ；这两个数中这一位有两个为 1 ，这一位就为 2 。（暂时先不考虑进位）

换句话说 在求和时，按位或操作计算时有一个 1 的 计算了一次，但有两个 1 的 也只计算了一次，但是两个 1 的应该计算两次，所以再加上按位与即为两数之和。

（我表达能力有限，好像说的不是很清楚）

由

移项得

代入得

因为这三项满足等式关系，所以想要满足 ,我们只需满足 即可

现在，重点来了，如何检验是否合法

我们设

如果把每个数的二进制看作是字符串，那么 每一个为 的位， 和 的那一位都一定为 ； 每一个为 的位， 和 的那一位最多只能有一个数 ( 或者 ) 为 ,既然这样，我们可以将 当做 。

当做

我们再将 拆成 和

如果 中的某一位为 ，那么 中的那一二进制位不能为 （如果那样, 就不等于 了，因为可能会涉及进位），也就是只有保证 为假， 才等于 。

所以

应为假。

所以结束

当 时，有合法解

#include<cstdio>
using namespace std;
long long T,a,b;
int main()
{
    freopen("solution.in","r",stdin);
    freopen("solution.out","w",stdout); 
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&a,&b);
        ((!((2*a-b)&(b-a)))&&(2*a-b)>0)?puts("Possible"):puts("Impossible");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}